package com.example.leetcode.trainingcamp.week4.Sunday;

/**
 * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 *
 * <p>此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 *
 * <p>
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sort-colors
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test75 {

    public void sortColors(int[] nums) {
        quickSort(0,nums.length-1,nums);
    }

    public void quickSort(int low,int high,int[] nums){
        if (low>high){
            return;
        }
        int i = low;
        int j = high;
        int temp = nums[low];
        while (i<j){
            while (i<j && nums[j]>= temp){
                j--;
            }
            while (i<j && nums[i]<=temp){
                i++;
            }
            if (i<j){
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        nums[low] = nums[i];
        nums[i] = temp;
        quickSort(low,i-1,nums);
        quickSort(i+1,high,nums);
    }
}

class Demo75{
  public static void main(String[] args) {
    int[] nums = {2,0,2,1,1,0};
    Test75 t = new Test75();
    t.sortColors(nums);
    for (int n:nums ) {
      System.out.print(n+" ");
    }
  }
}